package com.topInterview;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/20 19:22
 */
public class Leecode91_decode {
    public int numDecodings(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        int N = s.length();
        int[] dp = new int[N + 1];
        dp[N] = 1;
        char[] chars = s.toCharArray();
        //dp[i]依赖dp[i+1]和dp[i+2]的位置
        for (int i = N - 1; i >= 0; i--) {
            if (chars[i] != '0') {
                dp[i] = dp[i + 1];
                if (i + 1 == chars.length) {
                    continue;
                }
                int num = (chars[i] - '0') * 10 + (chars[i + 1] - '0');
                if (num <= 26) {
                    dp[i] += dp[i + 2];
                }
            }
        }

        return dp[0];
    }


    public int process(char[] chars, int index) {
        if (index == chars.length) {
            return 1;
        }

        if (chars[index] == '0') {
            return 0;
        }

        int ways = process(chars, index + 1);
        if (index + 1 == chars.length) {
            return ways;
        }

        int num = (chars[index] - '0') * 10 + (chars[index + 1] - '0');
        if (num <= 26) {
            ways += process(chars, index + 2);
        }
        return ways;
    }
}
